#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <climits>

using namespace std;

vector<int> generateRandomArray(int n) {
	vector<int> arr(n);
	srand(time(0));
	for (int i = 0; i < n; i++) {
		//随机-100到100
		arr[i] = rand() % 201 - 100;
	}
	return arr;
}

pair<int, int> findMax(const vector<int>& arr) {//
	int max_current = arr[0];//临时
	int max_global = arr[0];
	int start = 0, end = 0, temp_start = 0;//标记区间

	for (int i = 1; i < arr.size(); i++) {
		if (max_current > 0) {
			//求和
			max_current += arr[i];
		}
		else {
			//刷新区间
			max_current = arr[i];
			temp_start = i;
		}

		if (max_current > max_global) {
			max_global = max_current;
			start = temp_start;
			end = i;//标记区间结束
		}
	}
	return { start, end };
}

int main() {
	int n = 100;
	//首先生成随机数
	vector<int> arr = generateRandomArray(n);

	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;

	//找到最大连续子片段
	pair<int, int> result = findMax(arr);

	//计算和
	int sum = 0;
	for (int i = result.first; i <= result.second; i++) {
		sum += arr[i];
	}

	cout << "最大连续子片段从" << result.first << "到" << result.second << endl;
	cout << "和为" << sum << endl;

	return 0;
}